package backtrack;


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @Description 三数之和 (不建议使用回溯算法求解,回溯不是本题的最优解)
 * @Author Firenut
 * @Date 2023-02-14 21:17
 */
public class T15_threeSum {



    // 这题用回溯比较麻烦，主要是测试用例中可能有重复的数，所以会导致得到的是重复解
    // 所以在递归终止条件: if (sum == 0 && temp.size() == 3) 加入temp前需要做去重的处理
    // 去重的方法是先对temp做排序
    // 所以效率是很低的,后面会超时
    // 测试用例:
    // [-1,0,1,2,-1,-4]

    // DFS
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();

    public List<List<Integer>> threeSum(int[] nums) {
        dfs(nums, 0, 0);
        return ans;
    }

    void dfs(int[]nums,int index,int sum){
        if (sum == 0 && temp.size() == 3) {
            List<Integer> t = new ArrayList<>(temp);
            Collections.sort(t);
            if (!ans.contains(t)) {
                ans.add(t);
            }
            return;
        }

        if (index >= nums.length) { // 到达最底层
            return;
        }
        if(temp.size()>3){
            return;
        }

        // 选
        temp.add(nums[index]);
        dfs(nums,index+1,sum+nums[index]);

        // 不选
        temp.remove(temp.size()-1);
        dfs(nums,index+1,sum);
    }
}
